import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SolutionInterview17_13 {

    static class Trie{
        Trie[] children=new Trie[26];
        boolean end;

        void insert(String word){
            Trie node=this;
            for (char c : word.toCharArray()) {
                if (node.children[c-'a']==null){
                    node.children[c-'a']=new Trie();
                }
                node=node.children[c-'a'];
            }
            node.end=true;
        }

        List<Integer> query(String word){
            List<Integer> list=new ArrayList<>();
            Trie node=this;
            for (int i=0;i<word.length();i++){
                char c=word.charAt(i);
                if (node.children[c-'a']==null){
                    return list;
                }
                node=node.children[c-'a'];
                if (node.end){
                    list.add(i+1);
                }
            }
            return list;
        }
    }

    public int respace(String[] dictionary, String sentence) {
        Trie trie=new Trie();
        for (String s : dictionary) {
            trie.insert(s);
        }
        List<Integer>[] lists=new ArrayList[sentence.length()];
        for (int i=0;i<sentence.length();i++){
            lists[i]=trie.query(sentence.substring(i));
        }
        int[] f=new int[sentence.length()+1];
        Arrays.fill(f,Integer.MAX_VALUE);
        f[0]=0;
        for (int i=0;i<sentence.length();i++){
            for (Integer integer : lists[i]) {
                f[i+integer]=Math.min(f[i+integer],f[i]);
            }
            f[i+1]=Math.min(f[i+1],f[i]+1);
        }
        return f[sentence.length()];
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview17_13().respace(new String[]{"looked","just","like","her","brother"},"jesslookedjustliketimherbrother"));
    }
}
